#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int* hilbert_coords_x;
int* hilbert_coords_y;
int n_coords;
char* curve;

int ipow(const int a, const int b);
static int get_curve_length(const int level);

void
make_hilbert_coords(const int level)
{
	int i,j,x,y;
	char* temp_curve;
	const int length = get_curve_length(level);

	n_coords = ipow(4,level);
	curve = (char*)malloc(length*sizeof(char)+1);
	if (curve==NULL) exit(1);
	temp_curve = (char*)malloc(length*sizeof(char)+1);
	if (temp_curve==NULL) exit(1);
	hilbert_coords_x = (int*)malloc(n_coords*sizeof(int));
	if (hilbert_coords_x==NULL) exit(1);
	hilbert_coords_y = (int*)malloc(n_coords*sizeof(int));
	if (hilbert_coords_y==NULL) exit(1);
	// the L-system axiom
	memset(curve,0x00,length);
	strcat(curve,"U");
	//printf("%s\n",curve);
	// generate the curve
	for (i=1; i<level; i++) {
		// reset temp_curve
		memset(temp_curve,0x00,length);
		for (j=0; j<strlen(curve); j++) {
			// the L-system rules
			if (curve[j] == 'U') {
				strcat(temp_curve,"DsUeUnC");
			} else if (curve[j] == 'D') {
				strcat(temp_curve,"UeDsDwA");
			} else if (curve[j] == 'C') {
				strcat(temp_curve,"AwCnCeU");
			} else if (curve[j] == 'A') {
				strcat(temp_curve,"CnAwAsD");
			} else if (curve[j] == 'n') {
				strcat(temp_curve,"n");
			} else if (curve[j] == 's') {
				strcat(temp_curve,"s");
			} else if (curve[j] == 'e') {
				strcat(temp_curve,"e");
			} else if (curve[j] == 'w') {
				strcat(temp_curve,"w");
			}
		}
		memcpy(curve,temp_curve,length);
		//printf("%s\n",curve);
	}
	// convert the curve into coords
	for (i=j=x=y=0; i<strlen(curve); i++) {
		if (curve[i] == 'U') {
			hilbert_coords_x[j] = x;
			hilbert_coords_x[j+1] = x;
			hilbert_coords_x[j+2] = x+1;
			hilbert_coords_x[j+3] = x+1;
			x++;
			hilbert_coords_y[j] = y;
			hilbert_coords_y[j+1] = y+1;
			hilbert_coords_y[j+2] = y+1;
			hilbert_coords_y[j+3] = y;
			j+=4;
		} else if (curve[i] == 'D') {
			hilbert_coords_x[j] = x;
			hilbert_coords_x[j+1] = x+1;
			hilbert_coords_x[j+2] = x+1;
			hilbert_coords_x[j+3] = x;
			hilbert_coords_y[j] = y;
			hilbert_coords_y[j+1] = y;
			hilbert_coords_y[j+2] = y+1;
			hilbert_coords_y[j+3] = y+1;
			y++;
			j+=4;
		} else if (curve[i] == 'C') {
			hilbert_coords_x[j] = x;
			hilbert_coords_x[j+1] = x-1;
			hilbert_coords_x[j+2] = x-1;
			hilbert_coords_x[j+3] = x;
			hilbert_coords_y[j] = y;
			hilbert_coords_y[j+1] = y;
			hilbert_coords_y[j+2] = y-1;
			hilbert_coords_y[j+3] = y-1;
			y--;
			j+=4;
		} else if (curve[i] == 'A') {
			hilbert_coords_x[j] = x;
			hilbert_coords_x[j+1] = x;
			hilbert_coords_x[j+2] = x-1;
			hilbert_coords_x[j+3] = x-1;
			x--;
			hilbert_coords_y[j] = y;
			hilbert_coords_y[j+1] = y-1;
			hilbert_coords_y[j+2] = y-1;
			hilbert_coords_y[j+3] = y;
			j+=4;
		} else if (curve[i] == 'n') {
			y--;
		} else if (curve[i] == 's') {
			y++;
		} else if (curve[i] == 'e') {
			x++;
		} else if (curve[i] == 'w') {
			x--;
		}
	}
	free(curve);
	free(temp_curve);
}

void
dump_hilbert_coords()
{
	int i;
	printf("    n|    x|    y\n-----------------\n");
	for (i=0; i<n_coords; i++) {
		printf("%5d|%5d|%5d\n",i,
				hilbert_coords_x[i],
				hilbert_coords_y[i]
		      );
	}
}

void
free_hilbert_coords()
{
	free(hilbert_coords_x);
	free(hilbert_coords_y);
}

int
ipow(const int a, const int b)
{
	if (b<=0) {
		return 1;
	} else {
		int i,n;
		n = a;
		for (i=1; i<b; i++)
			n *= a;
		return n;
	}
}

static int
get_curve_length(const int level)
{
	if (level < 2) {
		return 1;
	} else {
		int i,n;
		n=1;
		for (i=1; i<level; i++) {
			n = 4*n+3;
		}
		return n;
	}
}

/*
int
main( int argc, const char* argv[] )
{
	make_hilbert_coords(atoi(argv[1]));
	dump_hilbert_coords();
	free_hilbert_coords();
	return 0;
}
*/

